#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=365 lang=cpp
 *
 * [365] 水壶问题
 */

// @lc code=start
typedef pair<int, int> state;

struct state_hash {
    size_t operator()(const state & s) const {
        return hash<int>()(s.first) ^ hash<int>()(s.second);
    }
};

struct state_cmp {
    bool operator()(const state & s1, const state & s2) const {
        return s1.first == s2.first && s1.second == s2.second;
    }
};

class Solution {
public:

    // bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
    //     queue<state> q; unordered_set<state, state_hash, state_cmp> used;
    //     q.push({jug1Capacity, jug2Capacity}); used.insert({jug1Capacity, jug2Capacity});

    //     while (!q.empty()) {
    //         state s = q.front(); q.pop();
    //         if (s.first == targetCapacity || s.second == targetCapacity || s.first + s.second == targetCapacity) return true;

    //         if (!used.count({0, s.second})) {
    //             used.insert({0, s.second});
    //             q.push({0, s.second});
    //         }

    //         if (!used.count({s.first, 0})) {
    //             used.insert({s.first, 0});
    //             q.push({s.first, 0});
    //         }

    //         if (!used.count({jug1Capacity, s.second})) {
    //             used.insert({jug1Capacity, s.second});
    //             q.push({jug1Capacity, s.second});
    //         }

    //         if (!used.count({s.first, jug2Capacity})) {
    //             used.insert({s.first, jug2Capacity});
    //             q.push({s.first, jug2Capacity});
    //         }

    //         int sum = s.first + s.second;
    //         int a = min(jug1Capacity, sum);
    //         int b = max(sum - a, 0);
    //         if (!used.count({a, b})) {
    //             used.insert({a, b});
    //             q.push({a, b});
    //         }

    //         b = min(jug2Capacity, sum);
    //         a = max(sum - b, 0);
    //         if (!used.count({a, b})) {
    //             used.insert({a, b});
    //             q.push({a, b});
    //         }
    //     }
        
    //     return false;
    // }

    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (jug1Capacity + jug2Capacity < targetCapacity) return false;
        return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0;
    }

};
// @lc code=end

